package leetcode13;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author tyy
 * @Description 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
    如果不存在公共前缀，返回空字符串 ""。
    示例 1：
    输入：strs = ["flower","flow","flight"]
    输出："fl"
    链接：https://leetcode-cn.com/problems/longest-common-prefix
 * @Since 2021/10/5
 */
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int index = 0;
        String str = strs[0];// 第一个元素
        for (int i = 1; i < strs.length; i++) {
            String str1 = strs[i];// 后面的元素

            for (int j = 0; j < str1.length(); j++) {
                index = j;
                if (str.charAt(j) != str1.charAt(j)) {
                    break;
                }
            }
            str = str.substring(0, index);
            if (str.equals("")) {
                return str;
            }
        }
        return str;

    }
    public String longestCommonPrefix1(String[] strs) {
        if(strs.length==0)return "";
        //公共前缀比所有字符串都短，随便选一个先
        String s=strs[0];
        for (String string : strs) {
            while(!string.startsWith(s)){
                if(s.length()==0)return ""; // 可以不用判断
                //公共前缀不匹配就让它变短！
                s=s.substring(0,s.length()-1);
            }
        }
        return s;
    }
    public String longestCommonPrefix2(String[] strs) {
        if(strs==null||strs.length==0) return "";
        String str=strs[0];
        for(int i=1;i<strs.length;i++){
            while(strs[i].indexOf(str)!=0){
                str=str.substring(0,str.length()-1);
            }
        }
        return str;
    }
    public String longestCommonPrefix3(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        // 字典排序
        Arrays.sort(strs);
        // 取排序后第一个串
        String startStr = strs[0];
        // 取最后一个串与第一个串进行比较，取他们两个都有的公共前缀为最终结果
        while (!strs[strs.length - 1].startsWith(startStr)) {
            startStr = startStr.substring(0, startStr.length() - 1);
        }
        return startStr;
    }
    public static void main(String[] args) {
        String[] arr = {"MCMXCIV"};
        String i2 = new Solution().longestCommonPrefix(arr);
        System.out.println("i = " + i2);


    }
}
